package jianzhioffer

//剑指 Offer II 004. 只出现一次的数字
func singleNumber(nums []int) int {
	cnt := make([]int, 33)
	for _, v := range nums {
		if v < 0 {
			cnt[32]++
			v = -v
		}
		for j := 0; j < 32 && v > 0; j++ {
			if v&1 == 1 {
				cnt[j]++
			}
			v = v >> 1
		}
	}
	res := 0
	base := 1
	for i := 0; i < 32; i++ {
		if cnt[i]%3 > 0 {
			res += base
		}
		base *= 2
	}
	if cnt[32]%3 > 0 {
		res = -res
	}
	return res
}

//剑指 Offer II 005. 单词长度的最大乘积
func maxProduct(words []string) int {
	wordlen := make([][]bool, len(words))
	for i := range wordlen {
		wordlen[i] = make([]bool, 26)
	}
	compare := func(a string, b []bool) bool {
		for i := range a {
			if b[a[i]-'a'] {
				return false
			}
		}
		return true
	}
	for i := range words {
		for j := range words[i] {
			wordlen[i][words[i][j]-'a'] = true
		}
	}
	res := 0
	for i := range words {
		for j := range wordlen {
			if j != i && compare(words[i], wordlen[j]) {
				tmp := len(words[i]) * len(words[j])
				if tmp > res {
					res = tmp
				}
			}
		}
	}
	return res
}

//剑指 Offer II 008. 和大于等于 target 的最短子数组
func minSubArrayLen(target int, nums []int) int {
	last, sum := 0, 0
	res := len(nums) + 1
	for i := range nums {
		sum += nums[i]
		for ; last <= i; last++ {
			if sum < target {
				break
			}
			if i-last+1 < res {
				res = i - last + 1
			}
			sum -= nums[last]
		}
	}
	if res == len(nums)+1 {
		res = 0
	}
	return res
}

//713. 乘积小于K的子数组
func numSubarrayProductLessThanK(nums []int, k int) int {
	ans := 0
	for i := 0; i < len(nums); i++ {
		sum := 1
		for j := i; j < len(nums); j++ {
			sum *= nums[j]
			if sum < k {
				ans++
			} else {
				break
			}
		}
	}
	return ans
}

//剑指 Offer II 010. 和为 k 的子数组
func subarraySum(nums []int, k int) int {
	ans := 0
	for i := 0; i < len(nums); i++ {
		sum := 0
		for j := i; j < len(nums); j++ {
			sum += nums[j]
			if sum == k {
				ans++
			}
		}
	}
	return ans
}

//剑指 Offer II 011. 0 和 1 个数相同的子数组
func findMaxLength(nums []int) int {
	ans := 0
	zero, one := 0, 0
	dp := make([]int, len(nums))
	for i := 0; i < len(nums); i++ {
		if nums[i] == 0 {
			zero++
		} else {
			one++
		}
		dp[i] = one - zero
		if dp[i] == 0 {
			ans = i + 1
		}
	}
	m := make(map[int]int)
	for i := 0; i < len(dp); i++ {
		if _, ok := m[dp[i]]; !ok {
			m[dp[i]] = i
		} else {
			if i-m[dp[i]] > ans {
				ans = i - m[dp[i]]
			}
		}
	}
	return ans
}

//剑指 Offer II 015. 字符串中的所有变位词
func findAnagrams(s string, p string) []int {
	res := []int{}
	if len(s) < len(p) {
		return res
	}
	ch1, ch2 := [26]int{}, [26]int{}
	for i := range p {
		ch1[p[i]-'a']++
		ch2[s[i]-'a']++
	}
	for i := 0; i <= len(s)-len(p); i++ {
		if ch1 == ch2 {
			res = append(res, i)
		}
		ch2[s[i]-'a']--
		if i != len(s)-len(p) {
			ch2[s[i+len(p)]-'a']++
		}
	}
	return res
}

//剑指 Offer II 016. 不含重复字符的最长子字符串
func lengthOfLongestSubstring(s string) int {
	m := make(map[byte]int)
	left, right := 0, 0
	res := 0
	for right < len(s) {
		if m[s[right]] > 0 {
			m[s[left]]--
			left++
		} else {
			m[s[right]]++
			if right-left+1 > res {
				res = right - left + 1
			}
			right++
		}
	}
	return res
}

//剑指 Offer II 020. 回文子字符串的个数
func countSubstrings(s string) int {
	res := 0
	for i := 0; i < len(s); i++ {
		for j := 0; i-j >= 0 && i+j < len(s); j++ {
			if s[i-j] == s[i+j] {
				res++
			} else {
				break
			}
		}
	}
	for i := 0.5; i < float64(len(s)); i++ {
		for j := 0.5; i-j >= 0 && i+j < float64(len(s)); j++ {
			if s[int(i-j)] == s[int(i+j)] {
				res++
			} else {
				break
			}
		}
	}
	return res
}

//剑指 Offer II 021. 删除链表的倒数第 n 个结点
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	pre := &ListNode{
		Val:  0,
		Next: head,
	}
	res := pre
	node1 := head
	cnt := n
	for node1 != nil {
		if cnt > 0 {
			cnt--
		} else {
			pre = pre.Next
		}
		node1 = node1.Next
	}
	pre.Next = pre.Next.Next
	return res.Next
}

//剑指 Offer II 022. 链表中环的入口节点
func detectCycle(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil {
		slow = slow.Next
		fast = fast.Next
		if fast != nil {
			fast = fast.Next
		}
		if fast == slow {
			break
		}
	}
	if fast == nil {
		return nil
	}
	res := head
	for res != slow {
		res = res.Next
		slow = slow.Next
	}
	return res
}

//445. 两数相加 II
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	stack1, stack2 := []int{}, []int{}
	for l1 != nil {
		stack1 = append(stack1, l1.Val)
		l1 = l1.Next
	}
	for l2 != nil {
		stack2 = append(stack2, l2.Val)
		l2 = l2.Next
	}
	carry := 0
	var node *ListNode
	for len(stack1) > 0 && len(stack2) > 0 {
		num1 := stack1[len(stack1)-1]
		num2 := stack2[len(stack2)-1]
		stack1 = stack1[:len(stack1)-1]
		stack2 = stack2[:len(stack2)-1]
		res := num1 + num2 + carry
		carry = res / 10
		res = res % 10
		tmp := &ListNode{
			Val:  res,
			Next: node,
		}
		node = tmp
	}
	for len(stack1) > 0 {
		num1 := stack1[len(stack1)-1]
		stack1 = stack1[:len(stack1)-1]
		res := num1 + carry
		carry = res / 10
		res = res % 10
		tmp := &ListNode{
			Val:  res,
			Next: node,
		}
		node = tmp
	}
	for len(stack2) > 0 {
		num1 := stack2[len(stack2)-1]
		stack2 = stack2[:len(stack2)-1]
		res := num1 + carry
		carry = res / 10
		res = res % 10
		tmp := &ListNode{
			Val:  res,
			Next: node,
		}
		node = tmp
	}
	if carry != 0 {
		tmp := &ListNode{
			Val:  carry,
			Next: node,
		}
		node = tmp
	}
	return node
}

func reorderList(head *ListNode) {
	if head == nil {
		return
	}
	nodes := []*ListNode{}
	for node := head; node != nil; node = node.Next {
		nodes = append(nodes, node)
	}
	i, j := 0, len(nodes)-1
	for i < j {
		nodes[i].Next = nodes[j]
		i++
		if i == j {
			break
		}
		nodes[j].Next = nodes[i]
		j--
	}
	nodes[i].Next = nil
}

type Node struct {
	Val   int
	Prev  *Node
	Next  *Node
	Child *Node
}

func flatten(root *Node) *Node {
	temp := root
	for temp != nil {
		if temp.Child != nil {
			next := temp.Next

			temp.Next = temp.Child
			temp.Child.Prev = temp
			temp.Child = nil
			for n1 := temp; n1 != nil && next != nil; n1 = n1.Next {
				if n1.Next == nil {
					n1.Next = next
					next.Prev = n1
					break
				}
			}
		}
		temp = temp.Next
	}
	return root
}

//剑指 Offer II 029. 排序的循环链表
func insert(aNode *Node, x int) *Node {
	head := aNode
	if aNode == nil {
		aNode = &Node{
			Val:  x,
			Next: nil,
		}
		aNode.Next = aNode
	}
	for head != nil {
		if x >= head.Val && x <= head.Next.Val {
			newNode := &Node{
				Val:  x,
				Next: head.Next,
			}
			head.Next = newNode
			break
		}else if head.Next.Val<head.Val||head.Next==aNode {
			if x >= head.Val || x <= head.Next.Val {
				newNode := &Node{
					Val:  x,
					Next: head.Next,
				}
				head.Next = newNode
				break
			}
		}
		head = head.Next
	}
	return aNode
}
